"""
@Project ：Python_learning 
@File    ：面试17.18.最短超串.py
@Author  ：zhupp
@Date    ：2024/12/15 18:02 
"""
from collections import Counter


def isContains(win_map, s_map):
    # 只有当win_map中每个元素的数量都不小于s_map中对应元素的数量时才返回True
    return all(win_map[key] >= s_map[key] for key in s_map)


class Solution:
    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:
        if len(small) > len(big):
            return []
        s_map = Counter(small) #samll中各个元素出现的次数
        win_map = {}
        #滑动窗口中small的元素出现的次数
        for key in s_map:  #初始化win_map，让里面small中的元素出现在win_map中
            if key not in win_map:
                win_map[key] = 0

        # 初始化左指针
        left = 0
        # 初始化最短子串的长度(尽可能是一个不满足的条件的最大值)
        min_len = len(big) + 1

        start = end = 0
        # 移动滑动窗口
        for right in range(len(big)):
            if big[right] in s_map:  # 如果长字符串中的right上的元素在s_map中
                win_map[big[right]] += 1  # 就让win_map中的该元素出现次数加一
            while isContains(win_map,s_map): # 验证窗口中的元素是否包含small
                if min_len > right - left + 1:
                    min_len = right - left + 1 # min_len为当前窗口长度
                    start = left
                    end = right         # 记录最后一次更新min_len时的左右指针值
                if big[left] in win_map: #
                    win_map[big[left]] -= 1
                left += 1
        if min_len == len(big) + 1:
            return []
        return [start, end]